import java.util.Arrays;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution300 {

    public static void main(String args[]){
        Solution300 s = new Solution300();
        System.out.println(s.lengthOfLIS(new int[]{1,3,6,7,9,4,10,5,6}));
    }

    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] dp = new int[n];
        int maxv = 1;
        for(int i = 0 ; i < n ; i ++) {
            dp[i] = 1;
        }
        for(int i = 0 ; i < n ; i ++){
            for(int j = i + 1; j < n ; j ++){
                if(nums[j] > nums[i]){
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    maxv = Math.max(maxv, dp[j]);
                }
            }
        }

        return maxv;
    }
}
